import java.util.Scanner;

/**
 * Created with IDEA
 * author:ju bai
 * Date:2021/5/17
 * Time:8:27
 **/
public class Main1 {
    /**
     * 每日一题-星际密码
     * @param args
     */
    public static void main(String[] args) {
        //初始化
        int[] nums = new int[10001];
        nums[1]=1;
        nums[2]=2;
        for (int i = 3; i < 10001; i++) {
            nums[i] = nums[i-1]+nums[i-2];//斐波那契数列
            nums[i] = nums[i]%10000;//取最后四位的值
        }
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            StringBuilder sb = new StringBuilder();
            int n = sc.nextInt();
            for (int i = 0; i < n; i++) {
                int xi = sc.nextInt();
                sb.append(String.format("%04d",nums[xi]));//格式化输出，表示只输出四位，不足填充0
            }
            System.out.println(sb);
        }
    }
}
